package offer_test_40;

//：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
//要求时间复杂度是O（n），空间复杂度为O（1）；
//思路，异或操作^， 相同的数字异或的结果为0
public class twenty_NumberAppearOnce {
	public static void main(String[] args) {
		int[] array = { 2, 4, 3, 6, 3, 2, 5, 5 };
		findnumappearonce(array);
	}

	public static void findnumappearonce(int[] array) {
		if (array == null)
			return;
		int number = 0;
		for (int i : array)
			number ^= i;
		int index = findFirstBitIs1(number);
		int number1 = 0;
		int number2 = 0;
		for (int i : array) {
			if (isBit1(i, index))
				number1 ^= i;
			else
				number2 ^= i;
		}
		System.out.println(number1 + " " + number2);
	}

	public static boolean isBit1(int i, int k) {
		i = i >> k;
		if ((i & 1) == 0) {
			return true;
		} else {
			return false;
		}
	}

	public static int findFirstBitIs1(int num) {
		int rs = 0;
		while ((num & 1) == 0) {
			num = num >> 1;
			rs++;
		}
		return rs;
	}
}
